package arithmetic.leetCode;

/**
 * @author dycong
 * @date 2019/10/29 8:40
 * <p>
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 * <p>
 * 输入为非空字符串且只包含数字 1 和 0。
 * <p>
 * 示例 1:
 * <p>
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 * <p>
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-binary
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class AddBinary_67 {

    public static void main(String[] args) {
        String a = "11", b = "1";
//        String a = "1010", b = "1011";

        System.out.println(addBinary(a, b));
    }

    public static String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length();
        int j = b.length();
        int carry = 0;
        while (i > 0 || j > 0) {
            int sum = 0;
            if (i > 0) sum += a.charAt(--i) - '0';
            if (j > 0) sum += b.charAt(--j) - '0';
            sum += carry;

            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry > 0) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }


}
